#include <stdio.h>

void shellSort(int arr[], int n)
{
    int gap, i, j;

    gap = 1;
    while (gap < n / 3)
    {
        gap = 3 * gap + 1;
    }

    while (gap > 0)
    {
        for (i = gap; i < n; i++)
        {
            int temp = arr[i];
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
            {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
        gap = (gap - 1) / 3;
    }
}

int main(int argc, char const *argv[])
{
    /* code */
    int arr[] = {12, 34, 54, 2, 3, 1, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Before sorting: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    shellSort(arr, n);

    printf("After sorting: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}
